#include <bits/stdc++.h>

using namespace std;

// 缺失的第一个正数
// 给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
// 请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
// 测试链接 : https://leetcode.cn/problems/first-missing-positive/

class Solution 
{
public:
    int firstMissingPositive(vector<int>& nums) 
    {
        // l 的左边，都是做到 i 位置上放着 i + 1 的区域
		// 永远盯着 l 位置的数字看，看能不能扩充(l++)
        int l = 0, r = nums.size();
        // [r....]垃圾区
		// 最好的状况下，认为 1~r 是可以收集全的，每个数字收集 1 个，不能有垃圾
		// 有垃圾呢？预期就会变差(r--)
        while(l < r)
        {
            if(nums[l] == l + 1) 
                ++l;
            else if(nums[l] <= l || nums[l] > r || nums[nums[l] - 1] == nums[l])
                swap(nums[l], nums[--r]);
            else
                swap(nums[l], nums[nums[l] - 1]);
        }
        return l + 1;
    }
};